import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    public  static ArrayList<String> Permutation(String str) {
        if(str.length()==0)
            return null;
        char[] array = str.toCharArray();
        return Permutation1("", array,0,str.length()-1);
    }

    static void exchange(int start, int i, char[] array){
        char temp = array[start];
        array[start] = array[i];
        array[i] = temp;
    }
    static ArrayList<String> list = new ArrayList<>();
    public static ArrayList<String> Permutation1(String pre, char[] array, int start, int end) {
        if(start>=end){
            list.add(pre+String.valueOf(array[start]));
            return list;
        }
        Permutation1(pre+String.valueOf(array[start]), array,start+1,end);//a+后面的变化拼成结果

        //排序，从start+1到end排个序。

        for(int i=start+1 ;i<=end;i++){
            if(array[start]!=array[i]){
                exchange(start,i,array);
                Permutation1(pre+String.valueOf(array[start]),array,start+1,end);//a与后面换位，拼结果
                exchange(start,i,array);
            }
        }
        Collections.sort(list);
        return list;
    }
    public static void main(String args[]){
        String a = "abc";
        char[] array = a.toCharArray();
        List<String> temp = Permutation(a);
        System.out.println("HAHA");
    }

}

